package main

import (
	"fmt"
	. "go_data_structures_and_algorithms/system_class/section10/pojo"
	"math"
)

/*
1--首先判断两条链表有是有环还是无环，再判断有无相交
找到链表有环的情况如下列所示
（1）利用快慢指针解决，快指针跳两步，慢指针每次跳两步，如果有环，那么快指针一定会在环内和慢指针相遇，

（2）而且慢指针最多会在环内走两圈，一定会和快指针相遇；

（3）如果相遇后，快指针回到链首，慢指针位置不变，两者每次都走一步，则她们一定会在环的入口处相遇

（4）如果快慢指针刚好在环的入口处相遇，那么环内和环外结点的数量刚好相等

情况一:两个都无环，判断他们是否相交
直接遍历完两个链表如果尾结点不相等说明两个链表不相交，如果相交的话就先找出哪个长度长，然后直接将长从头缩短到跟短的一样长，然后开始同时Next往下走找出第一个相交节点
情况二：一个有环一个无环，肯定不相交忽略

情况三：
分析：如果两个链表都有环，要么不相交，要么相交共用环，对于共用环，也有两种情况：

两者共用同一个入环结点，此时他们的相交结点只有一个，如下图甲
两者的入环结点不是同一个, 但此时两个链表分别的入环结点都可以叫做相交结点，如图乙

*/

func main() {
	// 1->2->3->4->5->6->7->null

	head1 := NewNode(1)
	head1.Next = NewNode(2)
	head1.Next.Next = NewNode(3)
	head1.Next.Next.Next = NewNode(4)
	head1.Next.Next.Next.Next = NewNode(5)
	head1.Next.Next.Next.Next.Next = NewNode(6)
	head1.Next.Next.Next.Next.Next.Next = NewNode(7)

	// 0->9->8->6->7->null
	head2 := NewNode(0)
	head2.Next = NewNode(9)
	head2.Next.Next = NewNode(8)
	head2.Next.Next.Next = head1.Next.Next.Next.Next.Next // 8->6

	fmt.Println(getIntersectNode(head1, head2).Value)

	// 1->2->3->4->5->6->7->4...
	head1 = NewNode(1)
	head1.Next = NewNode(2)
	head1.Next.Next = NewNode(3)
	head1.Next.Next.Next = NewNode(4)
	head1.Next.Next.Next.Next = NewNode(5)
	head1.Next.Next.Next.Next.Next = NewNode(6)
	head1.Next.Next.Next.Next.Next.Next = NewNode(7)
	head1.Next.Next.Next.Next.Next.Next = head1.Next.Next.Next // 7->4

	// 0->9->8->2...
	head2 = NewNode(0)
	head2.Next = NewNode(9)
	head2.Next.Next = NewNode(8)
	head2.Next.Next.Next = head1.Next // 8->2

	fmt.Println(getIntersectNode(head1, head2).Value)

	// 0->9->8->6->4->5->6..
	head2 = NewNode(0)
	head2.Next = NewNode(9)
	head2.Next.Next = NewNode(8)
	head2.Next.Next.Next = head1.Next.Next.Next.Next.Next // 8->6

	fmt.Println(getIntersectNode(head1, head2).Value)

}

func getLoopNode(head *Node) *Node {

	if head == nil || head.Next == nil || head.Next.Next == nil {
		return nil
	}
	slowPoint := head.Next
	quickPoint := head.Next.Next

	for quickPoint != slowPoint {
		if quickPoint.Next == nil || quickPoint.Next.Next == nil {
			return nil
		}
		quickPoint = quickPoint.Next.Next
		slowPoint = slowPoint.Next

	}
	quickPoint = head

	for quickPoint != slowPoint {
		quickPoint = quickPoint.Next
		slowPoint = slowPoint.Next
	}

	return quickPoint

}

func getIntersectNode(head1 *Node, head2 *Node) *Node {

	if head1 == nil || head2 == nil {
		return nil
	}
	node1 := getLoopNode(head1)
	node2 := getLoopNode(head2)

	if node1 == nil && node2 == nil {
		return situation1(head1, head2)
	} else if node1 != nil && node2 != nil {
		return situation3(head1, node1, head2, node2)
	}
	return nil
}

// 情况一:两个都无环，判断他们是否相交
func situation1(head1 *Node, head2 *Node) *Node {
	n1 := 0
	n2 := 0
	head1Back := head1
	head2Back := head2
	if head1 == nil && head2 == nil {
		return nil
	}
	var longPoint *Node = nil
	var shortPoint *Node
	for head1Back.Next != nil {
		head1Back = head1Back.Next
		n1++
	}
	for head2Back.Next != nil {
		head2Back = head2Back.Next
		n2++
	}

	if head1Back != head2Back {
		return nil
	}
	if n1 > n2 {
		longPoint = head1
		shortPoint = head2

	} else {
		longPoint = head2
		shortPoint = head1
	}

	for i := int(math.Abs(float64(n1 - n2))); i > 0; i-- {
		longPoint = longPoint.Next
	}

	for longPoint != shortPoint {
		longPoint = longPoint.Next
		shortPoint = shortPoint.Next
	}
	return longPoint

}

//情况三：
//分析：如果两个链表都有环，要么不相交，要么相交共用环，对于共用环，也有两种情况：

func situation3(head1 *Node, loop1 *Node, head2 *Node, loop2 *Node) *Node {

	if loop1 == loop2 {
		n1 := 0
		n2 := 0
		head1Back := head1
		head2Back := head2
		var longPoint *Node = nil
		var shortPoint *Node
		for head1Back != loop1 {
			head1Back = head1Back.Next
			n1++
		}
		for head2Back != loop2 {
			head2Back = head2Back.Next
			n2++
		}

		if head1Back != head2Back {
			return nil
		}
		if n1 > n2 {
			longPoint = head1
			shortPoint = head2

		} else {
			longPoint = head2
			shortPoint = head1
		}

		for i := int(math.Abs(float64(n1 - n2))); i > 0; i-- {
			longPoint = longPoint.Next
		}

		for longPoint != shortPoint {
			longPoint = longPoint.Next
			shortPoint = shortPoint.Next
		}
		return longPoint
	} else {
		//情况1和情况三 如果cur1遍历一圈找到自己了就说明他没有相交，如果遇到head2的入环节点就说明他们相交而且无论返回哪个相交节点都无所谓

		cur1 := loop1.Next
		for cur1 != loop1 {
			if cur1 == loop2 {
				return loop1
			}
			cur1 = cur1.Next
		}
		return loop1
	}

}
